package com.leetcode;

import java.util.*;

/**
 * 数对和
 * @author caiwei
 * @date 2021/9/9 15:37   
 */
public class LeetCode1624 {

    public static void main(String[] args) {

        int[] nums = new int[]{5,6,5,6};
        int target = 11;
        System.out.println(new LeetCode1624().pairSums(nums,target));
    }

    public List<List<Integer>> pairSums(int[] nums,int target){
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length <= 1) return list;
        //将数据存入map中，并记录重复次数
        Map<Integer,Integer> map = new HashMap<>();
        for(Integer key:nums){
            int val = map.getOrDefault(key, 0) + 1;
            map.put(key,val);
        }

        //遍历nums，寻找符合条件的数字
        for(Integer key:nums){
            int otherKey = target - key;
            if(map.containsKey(key) && map.containsKey(otherKey)){
                //当val与other相等的时候，看重复几次，构造出相应的数组，最后删除这个key
                if(key == otherKey){
                    int count = map.get(key);
                    for(int i=0;i<count/2;i++){
                        List<Integer> child = new ArrayList<>();
                        child.add(key);
                        child.add(otherKey);
                        list.add(child);
                    }
                    map.remove(key);
                }else{
                    int v1 = map.get(key);
                    int v2 = map.get(otherKey);
                    if(v1 == 1){
                        map.remove(key);
                    }else{
                        map.put(key,v1-1);
                    }
                    if(v2 == 1){
                        map.remove(otherKey);
                    }else{
                        map.put(otherKey,v2-1);
                    }
                    List<Integer> child = new ArrayList<>();
                    child.add(key);
                    child.add(otherKey);
                    list.add(child);
                }
            }
        }
        return list;
    }

}
